今天繼續來聽一堂課...

Restaurant reservation system

check requirement

Take care about user experince.

User want to choose scale about dating, then find the restaurant to order it.
So we need to consider about fast and reliable. (key point: make sure which is important in this system.)

Restaurants are also customers, we need analysis sytem / report system / management system... but it's too complex, we can focus on customer order a restaurant flow first.

try to design

At first, the restaurant info is not usually changed, so we can use CDN to let the page load fast.

User -> CDN

And, we will may have a lot of customer to otder together. We need use load balanacer to distribute request to each machine

User -> CDN -> LoadBalancer -> machine cluster

Choose noSql DB as our database, because the data is too large, and not need complex transaction

User -> CDN -> LoadBalancer -> machine cluster -> noSql (DynamoDB)

course example

design table first

Restaurant / Customer table / Reservation

consider data structure first to sure which database we need to use.

use loadblancer (because machine is stateless) (Geo-routing)

User -> LoadBalancer(Geo-routing) -> Machine cluster - > nosql <- SMS system (and add backup)

which I need to do

Consider more details about the all system. Design the table is also a good start.
Consider more about user flow.

好 一天一個範例思考
繼續刷題...

Minimum Number of Operations to Make Arrays Similar

Q: https://leetcode.com/problems/minimum-number-of-operations-to-make-arrays-similar/description/

class Solution {
    public long makeSimilar(int[] nums, int[] target) {
        Arrays.sort(nums);
        Arrays.sort(target);
        List<Integer> even1 = getEven(nums, true);
        List<Integer> odd1 = getEven(nums, false);
        List<Integer> even2 = getEven(target, true);
        List<Integer> odd2 = getEven(target, false);
        long diff = 0;
        for (int i = 0 ; i < even1.size(); i++) {
            if (even1.get(i) > even2.get(i)) {
                diff += even1.get(i) - even2.get(i);
            }
        }
        for (int i = 0 ; i < odd1.size(); i++) {
            if (odd1.get(i) > odd2.get(i)) {
                diff += odd1.get(i) - odd2.get(i);
            }
        }
        
        
        return diff / 2;
    }
    
    private List<Integer> getEven(int[] nums, boolean flag) {
        List<Integer> list = new ArrayList<>();
        for (int n : nums) {
            if (flag) {
                if (n % 2 == 0) {
                    list.add(n);                
                }   
            } else {
                if (n % 2 != 0) {
                    list.add(n);                
                }
            }
        }
        return list;
    }
}

divide it to even and odd to calculate

Partition List

Q: https://leetcode.com/problems/partition-list/description/

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode prevHead = new ListNode();
        ListNode afterHead = new ListNode();
        ListNode prevTail = prevHead;
        ListNode afterTail = afterHead;
        ListNode now = head;
        while(now != null) {
            if (now.val < x) {
                prevTail.next = now;
                prevTail = prevTail.next;
            } else {
                afterTail.next = now;
                afterTail = afterTail.next;
            }         
            now = now.next;
        }
        afterTail.next = null;
        prevTail.next = afterHead.next;
        return prevHead.next;
    }
}

Pascal's Triangle

Q: https://leetcode.com/problems/pascals-triangle/description/

/**
    row[0] = prevRow[0]
    row[1] = prevRow[0] + prevRow[1]
    .
    .
    row[n] = prevRow[n-1]
*/
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0;i < numRows;i++) {
            if (i == 0) {
                List<Integer> row = new ArrayList<>();
                row.add(1);
                result.add(row);
            } else {
                List<Integer> prevRow = result.get(i - 1);
                List<Integer> row = new ArrayList<>();
                for (int j = 0; j < prevRow.size() + 1;j++) {
                    if (j == 0) {
                        row.add(prevRow.get(0));
                    } else if (j == prevRow.size()) {
                        row.add(prevRow.get(prevRow.size() - 1));
                    } else {
                        row.add(prevRow.get(j - 1) + prevRow.get(j));
                    }
                }
                result.add(row);
            }
        }
        return result;
    }
}

不知道這題想考啥...

Single Number II

Q: https://leetcode.com/problems/single-number-ii/description/

class Solution {
    public int singleNumber(int[] nums) {
        int loner = 0;
        for (int shift = 0; shift < 32; shift++) {
            int bitSum = 0;
            for (int num : nums) {
                bitSum += (num >> shift) & 1;
            }
            int lonerBit = bitSum % 3;
            loner = loner | (lonerBit << shift);
        }
        return loner;
    }
}

LRU Cache

Q: https://leetcode.com/problems/lru-cache/

class ListNode {
    int key;
    int val;
    ListNode next;
    ListNode prev;

    public ListNode(int key, int val) {
        this.key = key;
        this.val = val;
    }
}

class LRUCache {
    int capacity;
    Map<Integer, ListNode> dic;
    ListNode head;
    ListNode tail;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        dic = new HashMap<>();
        head = new ListNode(-1, -1);
        tail = new ListNode(-1, -1);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (!dic.containsKey(key)) {
            return -1;
        }
        
        ListNode node = dic.get(key);
        remove(node);
        add(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if (dic.containsKey(key)) {
            ListNode oldNode = dic.get(key);
            remove(oldNode);
        }
        
        ListNode node = new ListNode(key, value);
        dic.put(key, node);
        add(node);
        
        if (dic.size() > capacity) {
            ListNode nodeToDelete = head.next;
            remove(nodeToDelete);
            dic.remove(nodeToDelete.key);
        }
    }
    
    public void add(ListNode node) {
        ListNode previousEnd = tail.prev;
        previousEnd.next = node;
        node.prev = previousEnd;
        node.next = tail;
        tail.prev = node;
    }
    
    public void remove(ListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}